package dynamicprogramming;

/**
 * @author DELL shiny
 * @create 2020/1/2
 */
public class DynamicProgramming {

    public int minPath(int[][] chess) {
        int row = chess.length;
        int col = chess[0].length;
        int[] dp = new int[col];
        dp[0] = chess[0][0];
        for(int j=1; j<col; j++) {
            dp[j] = dp[j - 1] + chess[0][j];
        }
        for(int i=1; i<row; i++) {
            for(int j=0; j<col; j++) {
                if(j == 0) {
                    dp[j] += chess[i][j];
                } else {
                    dp[j] = (dp[j] < dp[j - 1] ? dp[j] : dp[j - 1]) + chess[i][j];
                }
            }
        }
        return dp[col-1];
    }

    public static void main(String[] args) {
        DynamicProgramming dynamicProgramming=new DynamicProgramming();
    }
}
